package com.elong.algorithm;

import java.util.Collection;
import java.util.HashSet;
import java.util.SortedMap;
import java.util.TreeMap;

import com.elong.util.MD5Util;

/**
 * ConsistentHash
  * @Title: ConsistentHash
  * @Desription 一致性哈希实现 
  * @author Guanguo.Gao
  * @date 2015年3月6日 下午5:55:27
  * @param <T>
 */
public class ConsistentHash<T> {

    private final HashFunction hashFunction;
    
    /** 每个实体node对应的虚拟节点个数 **/
    private final int numberOfReplicas;
    
    /**
     * 哈希环
     *  key=node1-1,node1-2,... node1-n;  node2-1,node2-2,... node2..n;...对应的int
     *  value = node
     */
    private final SortedMap<Integer, T> circle = new TreeMap<>();
    
    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
	    Collection<T> nodes){
	this.numberOfReplicas = numberOfReplicas;
	this.hashFunction = hashFunction;
	for(T node : nodes){
	    add(node);
	}
    }

    /**
     * add
      * @Title: add
      * @Description: 添加节点到哈希环中
      * @param node
     */
    public void add(T node){
	for(int i = 0; i < numberOfReplicas; i++){
	    circle.put(hashFunction.hash(node.toString() + i), node);
	}
    }
    
    /**
     * remove
      * @Title: remove
      * @Description: 删除节点
      * @param node
     */
    public void remove(T node){
	for(int i = 0; i < numberOfReplicas; i++){
	    circle.remove(hashFunction.hash(node.toString() + i));
	}
    }
    
    /**
     * 获得一个最近的顺时针节点
     * @param key 为给定键取Hash，取得顺时针方向上最近的一个虚拟节点对应的实际节点
     * @return 节点对象
     */
    public T get(Object key){
	if(circle.isEmpty()){
	    return null;
	}
	int hash = hashFunction.hash(key);
	if(!circle.containsKey(hash)){
	    SortedMap<Integer, T> tailMap = circle.tailMap(hash);
	    hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
	}
	return circle.get(hash);
    }
    
    static class HashFunction {
	int hash(Object key){
	    return MD5Util.getMd5Str(key.toString()).hashCode();
	}
    }
    
    public static void main(String[] args) {
	HashSet<String> set = new HashSet<>();
	
	set.add("A");
	set.add("B");
	set.add("C");
	set.add("D");
    }
}
